package com.cet.qz.unit01.chapter1_3;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description: 动态数组实现双向队列
 * @author: 陈恩涛
 * @create: 2021-04-20 21:21
 **/
public class ResizingArrayDeque<Item> implements Iterable<Item> {

    private Item[] a = (Item[]) new Object[1];
    private int first, last, n;

    public boolean isEmpty() {
        return n == 0;
    }

    /**
     *方法描述： Deque长度
     *
     * @param
     * @return int
     * @author chenentao
     * @date 2021/4/21 9:32
     */
    public int size() {
        return n;
    }

    /**
     *方法描述：将原数组a中first到last-1的元素，拷贝到新数组的0到last-first-1
     *
     * @param max
     * @return void
     * @author chenentao
     * @date 2021/4/20 21:45
     */
    private void resize(int max) {
        Item[] items = (Item[]) new Object[max];
        int j = first;
        for (int i = 0; i < n; i++) {
            items[i] = a[j++];
        }
        a = items;
        first = 0;
        last = n;
    }

    public void pushLeft(Item item) {
        if (last == a.length) {
            if (n < a.length) {
                resize(a.length);
            } else {
                resize(2 * a.length);
            }
        }

        if (first == 0) {
            System.arraycopy(a, first, a, first + 1, n);
            a[first] = item;
            last++;
        } else {
            a[--first] = item;
        }
        n++;
    }

    public void pushRight(Item item) {
        if (last == a.length) {
            if (n < a.length) {
                resize(a.length);
            } else {
                resize(2 * a.length);
            }
        }
        a[last++] = item;
        n++;
    }

    public Item popLeft() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is null!");
        }
        Item item = a[first];
        a[first++] = null;
        n--;
        if (n == a.length / 4) {
            resize(a.length /2);
        }
        return item;
    }

    public Item popRight() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is null!");
        }
        Item item = a[--last];
        a[last] = null;
        n--;
        if (n == a.length / 4) {
            resize(a.length /2);
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ArrayDequeIterator(first,last);
    }

    class ArrayDequeIterator implements Iterator<Item> {

        private int head;
        private int tail;

        public ArrayDequeIterator(int head, int tail) {
            this.head = head;
            this.tail = tail;
        }

        @Override
        public boolean hasNext() {
            return head != tail;
        }

        @Override
        public Item next() {
            return a[head++];
        }

        @Override
        public void remove() {

        }
    }

    public static void main(String[] args) {
        ResizingArrayDeque<Integer> deque = new ResizingArrayDeque<>();
        deque.pushLeft(1);
        deque.pushLeft(2);
        deque.pushLeft(3);
        deque.pushRight(4);
        deque.pushRight(5);
        deque.pushLeft(6);
        deque.pushRight(7);
        deque.pushRight(8);
        deque.popLeft();
        deque.pushRight(9);
        for (Integer i : deque) {
            System.out.println(i);
        }
    }

}
